1. Field of the Invention
The present invention relates to method and system for efficiently handling Link State Advertisements (LSAs) over a data network. In particular, the present invention relates to method and system for providing selective LSA type blocking in a hub and spoke topology area of a data network.
2. Description of the Related Art
In a data communication networking environment, the flow of data through the network may be achieved by transmitting data from one node (or router) to the next until the destination for the data is reached. Typical routing protocols allow each router to determine the best path for forwarding data in the direction of the destination. In particular, each router performs calculations to determine the next hop router based on the known network topology. In link-state routing protocols, the existence of various nodes and connections (or links) in a network are advertised to other routers in the network. Thus, each router may be configured to learn the network topology. In turn, the knowledge of the network topology may be used by each router to determine the best “next hop” router to a particular destination. All routers in the network or in an area of the network perform similar calculations to identify the best next hop router for each destination in the network. The routers use this information to forward data to the destination specified.
An example of a link-state routing protocol is the Open Shortest Path First (OSPF) routing protocol which is an Interior Gateway Protocol (IGP) used to exchange routing information within an autonomous system generally intended for use in large networks. In particular, using link state algorithms, the OSPF routing protocol exchanges routing information between routers in the autonomous system. Routers may be configured to synchronize their topological databases, and once the routers are synchronized and the routing tables are built, the routers may be configured to flood topology information in response to some network topological change. For the OSPF routing protocol, the “best” path to a destination is the path that offers the least cost metric, and cost metrics may be configurable allowing preferred paths to be specified.
Each router operating under the OSPF routing protocol maintains an identical database describing the network topology to which it is connected. Using this topology database, each router may be configured to generate a routing table by constructing a shortest-path tree with the router at the root of the tree. The OSPF routing protocol is a dynamic routing protocol such that any changes in the network topology may be detected and the paths recalculated based on the new topology. Typically, all routers in an autonomous network run the OSPF routing protocol simultaneously, and the OSPF routing protocol allows multiple networks and routers to be grouped together. These groupings are commonly referred to as areas. Routers operating under the OSPF routing protocol may be configured to generate link state advertisements (LSAs) describing the local state of its links. Each LSA is flooded (or broadcast) throughout the area to the routers within the area such that the area's topology database includes the LSAs broadcast throughout the area.
Moreover, the specific topology of a particular area is not broadcast to other areas. Rather, a summary of the area is transmitted to other areas, thereby reducing the amount of link-state information transmitted through the network. When a router is connected to more than one area, it maintains a separate topology database for each connected area. A separate execution of the OSPF routing protocol's basic routing algorithm may be performed in each area. Additionally, routing within a particular area may be determined only by the topology of the particular area.
As link state routing protocols develop, new types of link state advertisements are created and existing link state advertisement formats are expanded or extended. New types of advertisements and extensions of existing advertisements increase the amount of data which must be exchanged between routers in a network. The increased data generates additional traffic on the network and requires additional memory or storage space within each router to store new data. Furthermore, the increased number of advertisements requires additional calculation performed by the routers to process the advertisements.
If the level of data generated and transmitted through the network in the form of advertisements becomes too large, the overall network performance may be reduced. Indeed, network routers may utilize a significant portion of their resources generating, receiving, processing and storing advertisements.
Link state protocols require that all routers in an area have the same detailed view of the topology. This mechanism works well for all topologies but it does not scale well in a very dense hub and spoke topology. Typical hub and spoke topology includes a high-end router which may be configured to serve many spoke routers (usually low end routers) on point-to-point networks. The spoke routers may also be connected to more than one hub router for redundancy purposes. Generally, the spoke routers do not communicate with each other, and all egress traffic is routed to the hub router. Indeed, changes in topology of a particular spoke router is of no interest to the other spoke routers as their immediate next hop will still be the hub router. Link state protocols by their nature propagates these changes to all spoke routers on the hub router if they belong to the same area.
Across enterprise networks, the spoke routers are often within the same area as it sometimes represent geographical distribution of their branch offices. Internet service providers (ISPs) and enterprise businesses increasingly have hub and spoke topologies at the access layer of their networks. For example, ISPs offering a pool of addresses to be used by DSL customers for instance, will have hub and spoke topologies. Another case may be for an enterprise business having a data center controlling several branch offices for credit card payment. In such hub and spoke configuration, all changes in topology on one spoke router are flooded to the hub and in turn, flooded to all the other spokes. As discussed above, the link state protocols cannot scale on very dense hubs. The changes in topology, inherent to connection and disconnection of a user may thus affect the whole area and cause constant full shortest path first (SPF) run calculations.
In view of the foregoing, it would be desirable to have a more scalable data network operating under the OSPF routing protocol in hub and spoke topologies.